// FRAOZO - 4a
// Declarations and functions for project #4

#include <iostream>
#include <limits.h>
#include "d_matrix.h"
#include "d_except.h"
#include <list>
#include <fstream>

using namespace std;

typedef int ValueType; // The type of the value in a cell
const int Blank = -1;  // Indicates that a cell is blank
 
const int SquareSize = 3;  //  The number of cells in a small square
                           //  (usually 3).  The board has
                           //  SquareSize^2 rows and SquareSize^2
                           //  columns.

const int BoardSize = SquareSize * SquareSize;

const int MinValue = 1;
const int MaxValue = 9;


const int squareNumberLookup[10][10] = {
   {0, 0,0,0, 0,0,0, 0,0,0},
   {0, 1,1,1, 2,2,2, 3,3,3},
   {0, 1,1,1, 2,2,2, 3,3,3},
   {0, 1,1,1, 2,2,2, 3,3,3},
   {0, 4,4,4, 5,5,5, 6,6,6},
   {0, 4,4,4, 5,5,5, 6,6,6},
   {0, 4,4,4, 5,5,5, 6,6,6},
   {0, 7,7,7, 8,8,8, 9,9,9},
   {0, 7,7,7, 8,8,8, 9,9,9},
   {0, 7,7,7, 8,8,8, 9,9,9}
}; //Used to determined what square a cell belongs to.  ie - top left cell
//   is determined with squareNumberLookup[1][1]

int numSolutions = 0;

class board
// Stores the entire Sudoku board
{
   public:
      board(int);
      void clear();
      void initialize(ifstream &fin);
      void print();
      bool isBlank(int, int);
      ValueType getCell(int, int);
	  bool isSolved();

      //Public members added
      void setCell(int, int, int);
      void clearCell(int, int);
      bool hasConflict(int, int, int) const;
      void printConflicts() const;
      
   private:

      // The following matrices go from 1 to BoardSize in each
      // dimension.  I.e. they are each (BoardSize+1) X (BoardSize+1)

      matrix<ValueType> value;
      matrix<bool> rowConflicts;
      matrix<bool> colConflicts;
      matrix<bool> squareConflicts;

      //Conflict-changing members. The user doesn't need access to these
      void updateConflicts(int, int);
      bool checkRow(int);
      bool checkCol(int);
      bool checkSquare(int);

      //Called by printConflicts()
      void printConflictMatrix(const matrix<bool> &) const;
};

bool board::isSolved()
{

	// Loop over every row/column to see if there are any conflics
	for (int idx = 1; idx < 10 ; idx++)
	{
		if (checkRow(idx) || checkCol(idx))
			return false;
	}
	
	// Loop over every cell to see if its blank
	for (int iX = 1; iX < 10; iX)
	{
		for (int iY = 1; iY < 10; iY)
		{
			if (isBlank(iX,iY))
				return false;
		}
	}
	
	// If we havent had any conflics, or blank cells
	// then the puzzle has been solved
	return true;
}

board::board(int sqSize)
   : value(BoardSize+1,BoardSize+1), rowConflicts(BoardSize+1,BoardSize+1),
     colConflicts(BoardSize+1,BoardSize+1), squareConflicts(BoardSize+1,BoardSize+1)
     // Board constructor
{
}

void board::clear()
{
   for (int row = 1; row <= BoardSize; row++)
      for (int col = 1; col <= BoardSize; col++)
      {
	 //Clear the cell, but don't update conflicts
	 value[row][col] = 0;
      }
}

void board::initialize(ifstream &fin)
// Read a Sudoku board from the input file.
{
   char ch;

   clear();
   for (int i = 1; i <= BoardSize; i++)
      for (int j = 1; j <= BoardSize; j++)
      {
	 fin >> ch;

	 // If the read char is not Blank
	 if (ch != '.')
	 {
            setCell(i,j,ch-'0');   // Convert char to int
	 }
      }
}

int squareNumber(int i, int j)
// Return the square number of cell i,j (counting from left to right,
// top to bottom.  Note that i and j each go from 1 to BoardSize
{
   // Note that (int) i/SquareSize and (int) j/SquareSize are the x-y
   // coordinates of the square that i,j is in.  

   return SquareSize * ((i-1)/SquareSize) + (j-1)/SquareSize + 1;
}

ostream &operator<<(ostream &ostr, vector<int> &v)
// Overloaded output operator for vector class.
{
   for (int i = 0; i < ((int)v.size()); i++)
      ostr << v[i] << " ";
   return ostr;
   //cout << endl;
}

ValueType board::getCell(int i, int j)
// Returns the value stored in a cell.  Throws an exception
// if bad values are passed.
{
   if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize)
      return value[i][j];
   else
      throw rangeError("bad value in getCell");
}

void board::printConflicts() const
//Prints the row, column, and square conflicts
// by calling printConflictMatrix on each type
{
   cout << "Row Conflicts:" << endl;
   printConflictMatrix(rowConflicts);

   cout << endl << "Column Conflicts:" << endl;
   printConflictMatrix(colConflicts);

   cout << endl << "Square Conflicts:" << endl;
   printConflictMatrix(squareConflicts);
   cout << endl;
}

void board::printConflictMatrix(const matrix<bool> &conflictMatrix) const
//Prints Passed a row, column, or square conflictMatrix in a
// grid-like format
{
   cout << "   ";

   //Print the possible digits...
   for (int digit=1; digit<=9; digit++)
      cout << digit << " ";
   cout << endl;
   cout << "--------------------" << endl;
	 
   //Foreach thing in the conflictMatrix
   for (int row=1; row<=9; row++)
   {
      cout << row << "| ";

      //Foreach digit
      for (int digit=1; digit<=9; digit++)
	 //print T if there's a conflict 
	 printf("%s ", conflictMatrix[row][digit] ? "T" : " ");

      cout << endl;
   }
}


void board::setCell(int i, int j, int entry) 
//Sets the cell, and updates conflicts
{
   value[i][j] = entry;
   updateConflicts(i, j);
}

void board::clearCell(int i, int j)
{
   //Same as setCell(i, j, 0);
   setCell(i, j, 0);
}

void board::updateConflicts(int row, int col)
//Updates the relevant row, column, and square conflicts
{
   checkRow(row);
   checkCol(col);

   int squareNumber;
   //Get square number associated with row, col
   squareNumber = squareNumberLookup[row][col];

   checkSquare(squareNumber);
}

bool board::checkRow(int row)
//Passed a row. Determines what digits would cause
//conflicts if placed in the given row
{
	bool digitConflicts = false;
   //foreach digit
   for (int digit=1; digit<=9; digit++)
   {
      rowConflicts[row][digit] = false;
	 
      //foreach col in row check digit
      for (int col=1; col<=9; col++)
	  {
		if (value[row][col] == digit)
		{
		    rowConflicts[row][digit] = true;
			digitConflicts = true;
	    }
	  }
   }
   return digitConflicts;
}

bool board::checkCol(int col)
//Passed a column. Determines what digits would cause
//conflicts if placed in the given col
{
	bool digitConflicts = false;
   //foreach digit
   for (int digit=1; digit<=9; digit++)
   {
      colConflicts[col][digit] = false;
	 
      //foreach row in col, check digit
      for (int row=1; row<=9; row++)
	  {
		  if (value[row][col] == digit)
		  {
			colConflicts[col][digit] = true;
			digitConflicts = true;
		  }
	  }
   }

   return digitConflicts;
}

bool board::checkSquare(int squareNumber)
//Passed a square number (1-9). Determines what digits would cause
//conflicts if placed in the given square
{
   int rowBegin;
   int colBegin;

   //set rowBegin and colBegin based on squareNumber
   switch (squareNumber)
   {
      case 1:
	 rowBegin=1; colBegin=1; break;
      case 2:
	 rowBegin=1; colBegin=4; break;
      case 3:
	 rowBegin=1; colBegin=7; break;

      case 4:
	 rowBegin=4; colBegin=1; break;
      case 5:
	 rowBegin=4; colBegin=4; break;
      case 6:
	 rowBegin=4; colBegin=7; break;

      case 7:
	 rowBegin=7; colBegin=1; break;
      case 8:
	 rowBegin=7; colBegin=4; break;
      case 9:
	 rowBegin=7; colBegin=7; break;
   }

   bool digitConflicts = false;
   //Foreach digit, check all cells in the current square
   for (int digit=1; digit<=9; digit++)
   {
      squareConflicts[squareNumber][digit] = false;

      //Foreach row in the current square
      for (int row=rowBegin; row < rowBegin+SquareSize; row++)

	 //Foreach col in the current square
	 for (int col=colBegin; col < colBegin+SquareSize; col++)

	    if (value[row][col] == digit)
		{
	       squareConflicts[squareNumber][digit] = true;
		   digitConflicts = true;
		}
   }
   return digitConflicts;
}

bool board::hasConflict(int row, int col, int digit) const
//Returns true if the digit would cause a conflict if set to the
//cell given by (row, col)
{
   int squareNumber = squareNumberLookup[row][col];
   //If row is true, don't try col, etc.
   return (rowConflicts[row][digit] || 
	   colConflicts[col][digit] ||
	   squareConflicts[squareNumber][digit] );
}

bool board::isBlank(int i, int j)
// Returns true if cell i,j is blank, and false otherwise.
{
	return getCell(i,j)==0;
	// We do not need to error check here, getCell checks for errors
   //if (i < 1 || i > BoardSize || j < 1 || j > BoardSize)
   //   throw rangeError("bad value in setCell");
}

void board::print()
// Prints the current board.
{
   for (int i = 1; i <= BoardSize; i++)
   {
      if ((i-1) % SquareSize == 0)
      {
	 cout << " -";
	 for (int j = 1; j <= BoardSize; j++)
	    cout << "---";
	 cout << "-";
	 cout << endl;
      }
      for (int j = 1; j <= BoardSize; j++)
      {
	 if ((j-1) % SquareSize == 0)
	    cout << "|";
	 if (!isBlank(i,j))
	    if ( getCell(i,j) )
	       cout << " " << getCell(i,j) << " ";
	    else 
	       cout << " _ ";
	 else
	    cout << "   ";
      }
      cout << "|";
      cout << endl;
   }

   cout << " -";
   for (int j = 1; j <= BoardSize; j++)
      cout << "---";
   cout << "-";
   cout << endl;
}

int main()
{
   ifstream fin;
   
   // Read the sample grid from the file.
   string fileName = "sudoku.txt";

   fin.open(fileName.c_str());
   if (!fin)
   {
      cerr << "Cannot open " << fileName << endl;
      return 1;
   }

   try
   {
      board b1(SquareSize);

      while (fin && fin.peek() != 'Z')
      {
	 b1.initialize(fin);
	 b1.print();
	 cout << endl;
	 b1.printConflicts();
	 cout << endl;
	 cout << "Is the board solved? " << b1.isSolved() << endl;
      }
   }
   catch  (indexRangeError &ex)
   {
      cout << ex.what() << endl;
      return 2;
   }

   int a = 0;
   cin >> a;
}
